# -*- coding: utf-8 -*-

"""我们有一个背包，背包总的承载重量是 Wkg。
现在我们有 n 个物品，每个物品的重量不等，并且不可分割。
我们现在期望选择几件物品，装载到背包中。
在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

///下述解决方案，运行时间较长"""

from copy import deepcopy
from queue import Queue, Empty

def knapsack01_backtrack_time(weights, maxw):
    """ids: 所有物品的下标
    inn：已经装包的物品下标集合
    outer：尚未装包的物品下标列表
    
    ！！！此回溯极为浪费时间，因为取物顺序 (1 -> 2) 与 (2 -> 1) 对下一步的取物影响完全一致，这样造成大量重复"""
    
    ids = set(range(len(weights)))
    largest_schemes = set()
    largest_weight = 0

    def weigh(inn):
        w = 0
        for i in inn:
            w += weights[i]
        return w

    def put(inn):
        nonlocal largest_weight
        outer = ids-set(inn)

        end = False
        cw = weigh(inn)
        if cw > maxw:
            inn.pop()
            cw = weigh(inn)
            end = True

        elif (not outer) or cw == maxw:
            end = True

        if end:
            if cw > largest_weight:
                largest_schemes.clear()
                largest_schemes.add(frozenset(inn))
                largest_weight = cw
            elif cw == largest_weight:
                largest_schemes.add(frozenset(inn))
            return

        for o in outer:
            new_inn = deepcopy(inn)
            new_inn.append(o)
            put(new_inn)
    
    put([])

    return largest_schemes, largest_weight

def knapsack01_backtrack(weights, maxw):
    def weigh(scheme):
        w = 0
        for i in scheme:
            w += weights[i]
        return w
    
    schemes = []
    last = len(weights)-1
    def put(i, scheme):
        if i > last:
            schemes.append(scheme)
            return
        
        if weigh(scheme)+weights[i] > maxw:
            schemes.append(scheme)
            return
        
        # 决策：不装i
        # scheme不变，保留原决策
        # 进入i+1决策
        put(i+1, scheme)

        # 决策：装i，能装则装
        # scheme变化，衍生出新决策
        # 进入i+1决策
        if weigh(scheme)+weights[i] <= maxw:
            new_scheme = deepcopy(scheme)
            new_scheme.append(i)
            put(i+1, new_scheme)
    
    # 开始决策第0个，决策前的决策状态是[]
    put(0, [])


    largest_schemes, largest_weight = [], 0
    for scheme in schemes:
        w = weigh(scheme)
        if w > largest_weight:
            largest_schemes.clear()
            largest_schemes.append(scheme)
            largest_weight = w
        elif w == largest_weight:
            largest_schemes.append(scheme)
    
    return largest_schemes, largest_weight

def kanpsack01_enumerate(weights, maxw):
    def weigh(scheme):
        cw = 0
        for i in scheme:
            cw += weights[i]
        return cw
    
    schemes = [[],[0]]
    for i in range(1, len(weights)):
        # 决策：不装
        # 原来方案保留

        # 决策：装
        # 衍生新方案
        new_schemes = []
        for scheme in schemes:
            cw = weigh(scheme)
            if cw + weights[i] <= maxw:
                new_scheme = deepcopy(scheme)
                new_scheme.append(i)
                new_schemes.append(new_scheme)
        
        schemes.extend(new_schemes)
    
    largest_schemes, largest_weight = [], 0
    for scheme in schemes:
        w = weigh(scheme)
        if w > largest_weight:
            largest_schemes.clear()
            largest_schemes.append(scheme)
            largest_weight = w
        elif w == largest_weight:
            largest_schemes.append(scheme)
    
    return largest_schemes, largest_weight

def kanpsack01_dynamic(weights, maxw):
    """为方便后面从根据状态表反推方案集，向重量列表中首位添加不影响计算重量为0的哨兵物品"""
    
    initial_status = [False for _ in range(maxw+1)]

    weights.insert(0, 0)
    
    # 哨兵物品重量为零，装与不装的决策结果重量状态都是0
    
    # 第一个物品决策状态
    start_status = deepcopy(initial_status)
    start_status[0] = True

    accumulate_status = [start_status]
    for i in range(1, len(weights)):
        pre_status = accumulate_status[-1]
        
        # 新决策要有新状态容器
        curr_status = deepcopy(initial_status)

        cw = weights[i]
        for totalw, isok in zip(range(maxw+1), pre_status):

            # 上次决策达到的重量位
            if isok:
                # 决策：不装
                # 状态保持老状态
                curr_status[totalw] = isok

                # 决策：装
                # 更新到达重量位
                if totalw+cw <= maxw:
                    curr_status[totalw+cw] = True
        
        accumulate_status.append(curr_status)
    
    # 选择可装的最大重量
    totalws = list(range(maxw+1))
    totalws.reverse()
    for totalw in totalws:
        if accumulate_status[-1][totalw]:
            break
    
    largestw = totalw
    # print(largestw)
    # for s in accumulate_status:
    #     print(s)
    
    # 根据选择的结果在状态标中反推方案集
    schemes = Queue()
    schemes.put((largestw, []))

    ids = list(range(1, len(weights)))
    ids.reverse()
    for i in ids:
        curr_w = weights[i]
        new_schemes = Queue()

        while True:
            try:
                scheme = schemes.get_nowait()
            except Empty:
                break
            
            state_w = scheme[0]
            # 如果不装呢？
            if accumulate_status[i-1][state_w]:
                # 如果第i-1行状态点为True，保留
                new_schemes.put(scheme)

            # 如果装呢？
            if accumulate_status[i-1][state_w-curr_w]:
                # 如果第i-1行状态点为True，衍生新方案
                new_scheme = (state_w-curr_w, deepcopy(scheme[1]))
                new_scheme[1].append(i)
                new_schemes.put(new_scheme)
        
        schemes = new_schemes

    return schemes, largestw


if __name__ == '__main__':
    weights = [1,2,3,4,5,6,7,8,9]
    maxw = 36
    from datetime import datetime
    
    print('-------------------------------')
    t11 = datetime.now()
    largest_schemes, largest_weight = knapsack01_backtrack(weights, maxw)
    t12 = datetime.now()
    print(t12-t11)
    print(largest_weight)
    for p in largest_schemes:
        print(p)
    
    print('-------------------------------')
    t21 = datetime.now()
    largest_schemes, largest_weight = kanpsack01_enumerate(weights, maxw)
    t22 = datetime.now()
    print(t22-t21)
    print(largest_weight)
    for scheme in largest_schemes:
        print(scheme)
    
    print('-------------------------------')
    t31 = datetime.now()
    largest_schemes, largest_weight = kanpsack01_dynamic(weights, maxw)
    t32 = datetime.now()
    print(t32-t31)
    print(largest_weight)
    while True:
        try:
            scheme = largest_schemes.get_nowait()
            print(scheme)
        except Empty:
            break
